home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / lzw.arc / LZWCOMM.C < prev    next >
Text File  |  1985-08-20  |  7KB  |  231 lines
  1. /* COMMLZW - ROUTINES COMMON TO LZWCOM AND LZWUNC                       */
  2. #include "stdio.h"
  3. #include "debug.h"
  4. #define FALSE    0
  5. #define TRUE     !FALSE
  6. #define TABSIZE  4096
  7. #define NO_PRED  0xFFFF
  8. #define EMPTY    0xFFFF
  9. #define NOT_FND  0xFFFF
  10. #define SECTSIZE 128
  11. #define CTRLZ '\032' /* ascii end of file */
  12. extern struct entry {
  13.   char used;
  14.   unsigned int next;                    /* index of next in collision list */
  15.   unsigned int predecessor;             /* 12 bit code                  */
  16.   unsigned char follower;
  17. } string_tab[TABSIZE];
  18.  
  19. /* h uses the 'mid-square' algorithm. I.E. for a hash val of n bits     */
  20. /* hash = middle binary digits of (key * key).  Upon collision, hash    */
  21. /* searches down linked list of keys that hashed to that key already.   */
  22. /* It will NOT notice if the table is full. This must be handled        */
  23. /* elsewhere                                                            */
  24.  
  25. unsigned h(pred,foll)
  26. /* returns the mid square of pred + foll                                */
  27.     unsigned int pred; unsigned char foll;
  28. {
  29.   long temp, local;             /* 32 bit receiving field for local^2   */
  30.   local = (pred + foll) | 0x0800;
  31.   temp = local * local;
  32.   local = (temp >> 6) & 0x0FFF;
  33.   return local;                 /* middle 12 bits of result             */
  34. }
  35.  
  36. unsigned eolist(index)
  37. /* return last element in a collision list                              */
  38. unsigned int index;
  39. {
  40.   register int temp;
  41.   while ( 0 != (temp = string_tab[index].next) )
  42.     index = temp;
  43.   return index;
  44. }
  45.  
  46. unsigned hash(pred,foll,update)
  47. unsigned int pred; unsigned char foll; int update;
  48. {
  49.   register unsigned int local, tempnext;
  50.   register struct entry *ep;
  51.   local = h(pred,foll);
  52.   if ( !string_tab[local].used )
  53.     return local;
  54.   else {
  55.   /* if collision has occured                                           */
  56.     local = eolist(local);
  57.  
  58.   /* search for free entry from local + 101 */
  59.     tempnext = (local + 101) & 0x0FFF; 
  60.     ep = &string_tab[tempnext];                 /* initialize pointer   */
  61.     while ( ep->used ) {
  62.       ++tempnext;
  63.       if ( tempnext == TABSIZE ) {
  64.         tempnext = 0;           /* handle wrap to beginning of table    */
  65.         ep = string_tab;        /* address of first element of table    */
  66.       } else
  67.         ++ep;                   /* point to next element in table       */
  68.     }
  69.     
  70.     /* put new tempnext into last element in collision list             */ 
  71.     if ( update )               /* if update requested                  */
  72.       string_tab[local].next = tempnext;
  73.     return tempnext;
  74.   } 
  75. }
  76.  
  77. /* unhash uses the 'next' field to go down the collision tree to find   */
  78. /* the entry corresponding to the passed key                            */
  79. /* passed key and returns either the matching entry # or NOT_FND        */
  80.  
  81. unsigned unhash(pred,foll)
  82. unsigned int pred; unsigned char foll;
  83. {
  84.   register unsigned int local, offset;
  85.   register struct entry *ep;    /* pointer to current entry             */
  86.  
  87.   local = h(pred,foll);         /* initial hash                         */
  88.   loop:
  89.     ep = &string_tab[local];
  90.     if ( (ep->predecessor == pred) && (ep->follower == foll) ) 
  91.       return local;
  92.     if ( ep->next == 0 )
  93.       return NOT_FND;
  94.     local = ep->next;
  95.   goto loop;
  96. }
  97.  
  98. init_tab() {
  99.   register unsigned int i;
  100.   setmem((char *)string_tab,sizeof(string_tab),0);
  101.   for (i = 0; i <= 255; i++) {
  102.     upd_tab(NO_PRED,i);
  103.   }
  104. }
  105.  
  106. #define UPDATE TRUE
  107.  
  108. upd_tab(pred,foll)
  109.   unsigned int pred, foll;
  110. {
  111.   register struct entry *ep;    /* pointer to current entry     */
  112.   /* calculate offset just once */
  113.   ep = &string_tab[ hash(pred,foll,UPDATE) ];
  114.   ep->used = TRUE;
  115.   ep->next = 0;
  116.   ep->predecessor = pred;
  117.   ep->follower = foll;
  118. }
  119.  
  120.  
  121. unsigned int inbuf = EMPTY;
  122. unsigned int outbuf = EMPTY;
  123.  
  124. /* getcode and putcode 'gallop' through input and output - they either  */
  125. /* output two bytes or one depending on the contents of the buffer.     */
  126.  
  127. getcode(fd) 
  128. FILE *fd;     {
  129.   register unsigned int localbuf, returnval;
  130.   if (EMPTY == inbuf) {         /* On code boundary                     */
  131.     if (EOF == (localbuf = getch(fd)) ) {       
  132.                                 /* H L1 byte - on code boundary         */
  133.       return EOF;
  134.     }
  135.     localbuf &= 0xFF;
  136.     if (EOF == (inbuf = getch(fd)) ) {  /* L0 Hnext                     */
  137.       return EOF;       /* The file should always end on code boundary  */
  138.     }
  139.     inbuf &= 0xFF;
  140.     DEBUGGER(fprintf(stderr,"%x and %x read\n",localbuf,inbuf);)
  141.     returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
  142.     DEBUGGER(fprintf(stderr,"returnval = %x\n",returnval);)
  143.     inbuf &= 0x000F;
  144.   } else {                      /* buffer contains nibble H             */
  145.     if (EOF == (localbuf = getch(fd)) )
  146.       return EOF;
  147.     localbuf &= 0xFF;
  148.     DEBUGGER(fprintf(stderr,"%x read, inbuf = %x\n",localbuf,inbuf);)
  149.     returnval = localbuf + ((inbuf << 8) & 0xF00);
  150.     inbuf = EMPTY;
  151.     DEBUGGER(fprintf(stderr,"returnval = %x\n",returnval);)
  152.   }
  153.   return returnval;
  154. }
  155.  
  156. putcode(fd,code)
  157. FILE *fd;
  158. unsigned int code;     {
  159.   register int localbuf;
  160.   if (EMPTY == outbuf) {
  161.     putch( ((code >> 4) & 0xFF),fd);    /* H L1                        */
  162.     outbuf = code & 0x000F;     /* L0                                   */
  163.   } else {
  164.     putch( ( ((outbuf << 4) & 0xFF0) + ((code >> 8) & 0x00F) ),fd );
  165.                                 /* L0prev H                             */
  166.     putch( (code & 0x00FF),fd);        /* L1 L0                        */
  167.     outbuf = EMPTY;
  168.   }
  169. }
  170. static int incount = 0, outcount = 0;
  171. static int ink = 0, outk = 0;
  172. putch(c,fp)
  173.     char c;
  174.     FILE *fp;
  175. {
  176.     if (outcount == 0)
  177.     {
  178.         reset_crc();
  179.     }
  180.     update_crc(c);
  181.     putc(c,fp);
  182.     outcount++;
  183.     if (outcount == 1024)
  184.     {
  185.         fprintf(stderr,"%dk written\r",++outk);
  186.         outcount = 0;
  187.         putw(get_crc(),fp);
  188.     }
  189. }
  190.  
  191. getch(fp)
  192.     FILE *fp;
  193. {
  194.     extern FILE *op;
  195.     register int returnc;
  196.     unsigned int crc;
  197.     if (incount == 0)
  198.     {
  199.         reset_crc();
  200.     }
  201.     if (EOF == (returnc = getc(fp)))
  202.         return EOF;
  203.     update_crc(returnc);
  204.     ++incount;
  205.     if (incount == 1024)
  206.     {
  207.         if (!isatty(fileno(op)))
  208.         {
  209.             fprintf(stderr,"%dk read\r",++ink);
  210.         }
  211.         incount = 0;
  212.         if (EOF == (crc = getw(fp)))
  213.             return EOF;
  214.         update_crc((crc & 0xFF));    /* lo byte */
  215.         update_crc(((crc >> 8) & 0xFF));    /* hi byte */
  216.         if (get_crc())
  217.         {
  218.             fprintf(stderr,"crc error - aborting");
  219.             exit(1);
  220.         }
  221.     }
  222.     return returnc;
  223. }
  224.  
  225. flushout(fd)
  226. FILE *fd;
  227. {
  228.     if ( EMPTY != outbuf)
  229.         putc(((outbuf << 4) & 0xFF0),fd);
  230. }
  231.